#include <iostream>
using namespace std;
#include <vector>


int Quick_select(vector<int>& nums, int begin, int end, int k)
{
    if (begin == end)
        return nums[k];

    int left = begin, right = end, keyi = begin;
    while (left < right)
    {
        while (left < right && nums[right] >= nums[keyi])
        {
            --right;
        }
        while (left < right && nums[left] <= nums[keyi])
        {
            ++left;
        }
        swap(nums[left], nums[right]);
    }

    swap(nums[left], nums[keyi]);
    keyi = left;

    //[begin,keyi-1] [keyi, end]
    if (k > keyi)
        return Quick_select(nums, keyi + 1, end, k);
    else
        return Quick_select(nums, begin, keyi, k);

}


int findKthLargest(vector<int>& nums, int k)
{
    int n = nums.size();
    return Quick_select(nums, 0, n - 1, n - k);

}

int main()
{
    vector<int> v = { 3,2,1,5,6,4 };
    int ret = findKthLargest(v, 2);

    cout << ret;
    return 0;
}